선형 계획법

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 역사
3. 표준형 및 쌍대성
- 3.1. 쌍대성 정리
4. 알고리즘
- 4.1. 단체법 (Simplex Method)
- 4.2. 내부점법 (Interior Point Method)
5. 활용
- 5.1. 한국에서의 활용 사례
6. 정수 계획법
7. 미해결 문제 및 최근 연구 동향
참조

1. 개요

선형 계획법은 선형 부등식 시스템을 푸는 문제에서 시작되어, 제2차 세계 대전 중 군사 작전의 효율성을 높이는 데 활용되었으며, 이후 다양한 산업 분야에서 활용되고 있는 최적화 기법이다. 조지 단치히가 개발한 단순법은 문제를 효율적으로 해결하는 알고리즘으로, 레오니트 칸토로비치, 바실리 레온티예프, 존 폰 노이만 등 여러 학자들의 연구를 통해 발전했다. 1979년 레오니트 카치얀은 다항 시간 내에 문제를 해결하는 알고리즘을 제시했고, 1984년 나렌드라 카르마르카는 내부점 방법을 도입하여 이 분야의 발전을 이끌었다. 선형 계획법은 표준형과 쌍대성을 가지며, 약한 쌍대성 정리와 강한 쌍대성 정리가 중요한 개념으로 작용한다. 단순법과 내부점법은 주요 알고리즘이며, 다양한 산업 분야에서 활용되고 있다. 정수 계획법은 모든 변수가 정수인 선형 계획법의 특수한 형태이며, 미해결 문제와 최근 연구 동향이 존재한다.

더 읽어볼만한 페이지

볼록 최적화 - 확률적 경사 하강법
확률적 경사 하강법은 기계 학습에서 목적 함수를 최소화하는 반복적 최적화 알고리즘으로, 대규모 데이터 세트에서 일부 데이터만 사용하여 경사를 추정하여 계산 비용을 줄이고, 서포트 벡터 머신, 로지스틱 회귀, 심층 신경망 등 다양한 모델 훈련에 활용되며, Adam과 같은 파생 최적화기가 널리 사용된다.
볼록 최적화 - 원추최적화
원추 최적화는 실수 벡터 공간에서 정의된 볼록 함수를 볼록 뿔 위에서 최소화하는 문제이며, 선형 계획법, 반정부호 계획법 등으로 축소될 수 있고 쌍대성 개념을 통해 쌍대 문제를 정의한다.
선형 계획법 - 자료 포락 분석
자료 포락 분석(DEA)은 여러 입력과 출력을 가진 의사결정단위(DMU)의 효율성을 측정하는 방법으로, 선형 계획법을 활용해 경험적 생산 기술 경계를 추정하며, 생산 함수 형태를 가정할 필요 없이 여러 입출력을 동시에 고려할 수 있지만, 변수 선택에 민감하다는 단점도 있다.
선형 계획법 - 일차 부등식
일차 부등식은 미지수의 최고차항이 1차인 부등식으로, ax > b, ax < b, ax ≥ b, ax ≤ b (단, a ≠ 0)의 형태로 표현되며, 해를 구하는 것은 부등식을 만족하는 미지수 x의 값을 찾는 것이고, 연립일차부등식은 각 부등식을 동시에 만족하는 해를 구하는 것을 목표로 한다.
운용 과학 - 계획
계획은 목표 달성을 위한 방법과 절차를 결정하는 과정으로, 개인적 목록 작성부터 국가적 자원 사용, 토지 이용 규제 등 다양한 형태로 나타나며, 상위-하향식, 하위-상향식, PDCA 사이클 등의 방법론을 활용하여 명확한 목표 설정, 효율적인 자원 관리, 위험 관리, 유연성을 필요로 한다.
운용 과학 - 알고리즘 설계
알고리즘 설계는 문제 해결을 위한 효율적인 절차나 방법을 구체화하는 과정으로, 문제 정의부터 문서화까지의 개발 단계를 거치며 분할 정복, 동적 계획법 등의 다양한 설계 기법들이 활용된다.

선형 계획법

2. 역사

푸리에는 1827년에 선형 부등식 시스템을 푸는 방법을 발표했으며,^[4] 그의 이름을 딴 푸리에-모츠킨 소거법이 있다.

1930년대 후반, 소련 수학자 레오니트 칸토로비치와 미국 경제학자 바실리 레온티예프는 독립적으로 선형 계획법의 실제 응용 분야를 탐구했다. 칸토로비치는 제조 일정에, 레온티예프는 경제적 응용 분야에 집중했다. 이들의 연구는 수십 년 동안 간과되었다.^[5] 칸토로비치의 연구는 처음에는 소련에서 무시되었다.^[6] 비슷한 시기에, 네덜란드계 미국 경제학자 T. C. 쿠프만스는 고전적인 경제 문제를 선형 계획법으로 공식화했다. 칸토로비치와 쿠프만스는 1975년 노벨 경제학상을 공동 수상했다.^[4] 1941년, 프랭크 로렌 히치콕 또한 수송 문제를 선형 계획법으로 공식화하고 나중에 단체법과 매우 유사한 해법을 제시했다.^[7]

제2차 세계 대전 중 선형 계획법은 중요한 도구로 등장하여 수송 물류, 일정 계획, 자원 배분 등 복잡한 전시 과제를 해결하는 데 광범위하게 사용되었다. 선형 계획법은 비용 및 자원 가용성과 같은 중요한 제약 조건을 고려하면서 이러한 프로세스를 최적화하는 데 매우 유용했다.

전시의 성공으로 인해 선형 계획법은 주목을 받게 되었다. 제2차 세계 대전 이후, 이 방법은 널리 인정을 받았고, 운영 연구에서 경제학에 이르기까지 다양한 분야의 초석이 되었다. 1930년대 후반 칸토로비치와 레온티예프의 간과된 공헌은 의사 결정 프로세스를 최적화하는 데 있어서 선형 계획법의 더 넓은 수용과 활용의 기초가 되었다.^[5]

1946년부터 1947년까지 조지 B. 단치히는 미국 공군에서 계획 문제를 해결하기 위해 일반적인 선형 계획법 공식을 독립적으로 개발했다.^[8] 1947년, 단치히는 대부분의 경우 선형 계획법 문제를 효율적으로 해결하는 단체법을 발명했다.^[8] 단치히가 자신의 단순법에 대해 논의하기 위해 존 폰 노이만과 만났을 때, 폰 노이만은 자신이 게임 이론에서 연구해 온 문제가 동등하다는 것을 깨닫고 즉시 이중성 이론을 추측했다.^[8] 전후 시대에, 많은 산업 분야에서 일상적인 계획에 이를 적용했다.

선형 계획법 문제는 1979년 레오니트 카치얀에 의해 처음으로 다항 시간 내에 해결할 수 있다는 것이 증명되었지만,^[9] 1984년 나렌드라 카르마르카가 선형 계획법 문제를 해결하기 위한 새로운 내부점 방법을 도입하면서 이 분야에서 더 큰 이론적이고 실용적인 혁신이 이루어졌다.^[10]

3. 표준형 및 쌍대성

선형 계획 문제는 문제 해결 알고리즘 개발을 위해 표준형으로 변환하는 것이 일반적이다. 표준형은 목적 함수를 최대화하고, 모든 제약 조건을 등식으로 표현하며, 모든 변수가 음수가 아닌 값을 갖도록 한다. 예를 들어 $x_1 + x_2 \le b_1$ 과 같은 부등식은 $x_1 + x_2 + s_1 = b_1,\,s_1 \ge 0$ 와 같은 등식과 간단한 조건으로 이루어진 형태로 바꿀 수 있고, $2x_1 + 3x_2 = b_1$ 과 같은 등식은 $2x_1 + 3x_2 \ge b_1$ 과 $2x_1 + 3x_2 \le b_1$ 의 두 부등식으로 변환할 수 있다.

농부 예제의 그래픽 솔루션 – 조건을 위반하는 영역을 음영 처리한 후, 점선이 있는 음영 처리되지 않은 영역의 정점에서 원점으로부터 가장 멀리 떨어진 곳이 최적의 조합을 제공한다. (토지 및 살충제 라인에 놓여 있다는 것은 수입이 비료가 아닌 토지 및 살충제에 의해 제한된다는 것을 의미한다)

농부가 밀이나 보리, 또는 이 둘의 조합으로 심을 농지 ''L'' 헥타르를 가지고 있고, ''F'' 킬로그램의 비료와 ''P'' 킬로그램의 살충제를 가지고 있다고 가정하자. 밀 1헥타르당 ''F''₁ 킬로그램의 비료와 ''P''₁ 킬로그램의 살충제가 필요하고, 보리 1헥타르당 ''F''₂ 킬로그램의 비료와 ''P''₂ 킬로그램의 살충제가 필요하다. S₁을 밀의 판매 가격, S₂를 보리의 판매 가격(헥타르당)이라고 하고, 밀과 보리에 심는 토지 면적을 각각 ''x''₁과 ''x''₂라고 표시하면, ''x''₁과 ''x''₂의 최적 값을 선택하여 이윤을 극대화할 수 있다. 이 문제는 다음과 같이 표준형 선형 계획법 문제로 표현할 수 있다.

최대화:	$S_1\cdot x_1+S_2\cdot x_2$	(총 밀 판매액 + 총 보리 판매액)을 최대화한다.
제약 조건:	$x_1 + x_2\leq L$	(총 면적 제한)
	$F_1\cdot x_1+F_2\cdot x_2\leq F$	(비료 제한)
	$P_1\cdot x_1 + P_2\cdot x_2\leq P$	(살충제 제한)
	$x_1\geq 0, x_2\geq 0$	(음수 면적을 심을 수 없음).

위 문제는 아래와 같이 행렬 형식으로 나타낼 수 있다.

: 최대화 $\begin{bmatrix} S_1 & S_2 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}$

: 제약 조건 $\begin{bmatrix} 1 & 1 \\ F_1 & F_2 \\ P_1 & P_2 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} \le \begin{bmatrix} L \\ F \\ P \end{bmatrix}, \, \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} \ge \begin{bmatrix} 0 \\ 0 \end{bmatrix}.$

3. 1. 쌍대성 정리

모든 선형 계획 문제에는 그에 대응하는 쌍대 문제가 있다. 쌍대 문제의 해는 원 문제의 해에 대한 정보를 담고 있기 때문에 매우 중요하고 유용하다.

원 문제가 최소화 문제라면 쌍대 문제는 최대화 문제가 되는데, 쌍대 문제의 최적값이 원 문제의 최적값보다 크지 않다는 것이 '''약한 쌍대성 정리'''이다. 사실 이 두 최적값이 같다는 것이 '''강한 쌍대성 정리'''이다.

표준형으로 나타낸 선형 계획 문제는 다음과 같다.

목적:		$\max_{\mathbf{x}} \mathbf{c}^T \mathbf{x}$
조건:	$\mathbf{Ax} \le \mathbf{b},$
조건:	$\mathbf{x} \ge 0.$

이에 대응하는 쌍대 문제는 다음과 같이 나타낼 수 있다.

목적:		$\min_{\mathbf{y}} \mathbf{b}^T \mathbf{y}$
조건:	$\mathbf{A^T y} \ge \mathbf{c},$
조건:	$\mathbf{y} \ge 0$

4. 알고리즘

선형 계획법 문제를 해결하는 대표적인 알고리즘으로는 단체법과 내부점법이 있다. 단체법은 제2차 세계 대전 당시 조지 댄치그가 군수 물자 보급의 최적화를 위하여 개발하였다. 내부점법은 1984년에 나렌드라 카르마르카가 개발했다.

선형 부등식 시스템을 푸는 문제는 조제프 푸리에가 1827년에 발표한 푸리에-모츠킨 소거법까지 거슬러 올라간다.^[4] 1930년대 후반, 소련의 레오니트 칸토로비치와 미국의 바실리 레온티예프는 선형 계획법의 실제 응용 분야를 연구했다. 칸토로비치는 제조 일정, 레온티예프는 경제적 응용 분야를 탐구했지만, 그들의 연구는 수십 년 동안 간과되었다.^[5]

제2차 세계 대전 중 선형 계획법은 수송 물류, 일정 계획, 자원 배분 등 복잡한 전시 과제를 해결하는 데 사용되었다. 종전 후, 이 방법은 운영 연구, 경제학 등 다양한 분야에서 활용되기 시작했다. 1930년대 후반 칸토로비치와 레온티예프의 공헌은 결국 선형 계획법의 활용 기반이 되었다.^[5]

칸토로비치의 연구는 처음에는 소련에서 무시되었다.^[6] 칸토로비치와 비슷한 시기에, 네덜란드계 미국 경제학자 찰링 쿠프만스는 고전적인 경제 문제를 선형 계획법으로 공식화했다. 칸토로비치와 쿠프만스는 1975년 노벨 경제학상을 공동 수상했다.^[4] 1941년, 프랭크 로렌 히치콕 또한 수송 문제를 선형 계획법으로 공식화하고 단체법과 유사한 해법을 제시했다.^[7]

1946년부터 1947년까지 조지 단치히는 미국 공군에서 계획 문제를 해결하기 위해 선형 계획법 공식을 개발했다.^[8] 1947년, 단치히는 단체법을 발명했다.^[8] 단치히가 존 폰 노이만과 만났을 때, 폰 노이만은 자신이 게임 이론에서 연구해 온 문제가 동등하다는 것을 깨닫고 이중성 이론을 추측했다.^[8] 단치히는 1948년 1월 5일에 공식적인 증명을 제공했다.^[6]

선형 계획법 문제는 1979년 레오니트 카치얀에 의해 처음으로 다항 시간 내에 해결할 수 있다는 것이 증명되었지만,^[9] 1984년 나렌드라 카르마르카가 내부점법을 도입하면서 이 분야에서 더 큰 혁신이 이루어졌다.^[10]

LP 솔버는 수송에서의 네트워크 플로우 문제(선형 계획 문제로 정식화할 수 있다)와 같은 산업의 다양한 문제의 최적화를 위해 널리 보급되어 있다.

4. 1. 단체법 (Simplex Method)

조지 댄치그가 개발한 단체법은 선형 계획법 문제를 해결하는 데 가장 널리 사용되는 알고리즘 중 하나이다.^[13]^[14] 이 방법은 실현가능영역(Feasible region)의 꼭짓점을 탐색하며 목적 함수 값을 개선해 나가는 방식으로 최적해를 찾는다.

심플렉스법은 1947년 조지 단치히가 개발하였으며, 다면체의 꼭짓점에서 실행 가능한 해를 구성한 다음, 목표 함수의 값이 감소하지 않는 꼭짓점을 따라 다면체의 모서리를 따라 이동하여 최적해에 도달할 때까지 문제를 해결한다.^[13]^[14] 많은 실제 문제에서 "스톨링"이 발생하는데, 이는 목표 함수가 증가하지 않는데도 많은 피벗이 수행됨을 의미한다.^[13]^[14] 드물게 실제 문제에서, 심플렉스 알고리즘의 일반적인 버전은 "사이클"을 돌 수 있다.^[14] 사이클을 피하기 위해 연구자들은 새로운 피벗 규칙을 개발했다.^[19]

실제로 심플렉스 알고리즘은 매우 효율적이며, ''사이클링''에 대한 특정 예방 조치를 취하면 전역 최적해를 찾을 수 있다고 보장한다. 심플렉스 알고리즘은 "임의" 문제를 효율적으로, 즉 3차 수의 단계로 해결하는 것으로 입증되었으며,^[15] 이는 실제 문제에서의 동작과 유사하다.^[13]^[16]

그러나 심플렉스 알고리즘은 최악의 경우 동작이 좋지 않다. 클리와 민티는 심플렉스 방법이 문제 크기에 대해 지수적인 단계 수를 거치는 일련의 선형 프로그래밍 문제를 구성했다.^[13]^[17]^[18] 실제로 한동안 선형 프로그래밍 문제가 다항 시간 내에, 즉 복잡도 클래스 P로 해결할 수 있는지 여부가 알려지지 않았다.

심플렉스법은 사용하는 피벗 규칙에 따라 성능이 좌우된다. 유한 번의 피벗으로 종료되는 것이 보장되는 규칙으로, Bland가 제안한 최소 첨자 규칙이 알려져 있다. Dantzig가 제안한 피벗 규칙은 문제의 규모에 대해 지수 시간이 걸리는 문제의 예가 있다는 것이 알려져 있다. 현재까지 선형 계획 문제를 다항 시간에 푸는 피벗 규칙의 존재 여부는 미해결 문제이다.

현재 의견은 심플렉스 기반 방법과 내부점 방법의 훌륭한 구현의 효율성이 선형 계획법의 일반적인 적용에서 유사하다는 것이다. 그러나 특정 유형의 선형 계획 문제의 경우, 한 유형의 솔버가 다른 솔버보다 더 나을 수 있으며(때로는 훨씬 더 나을 수 있으며), 내부점 방법과 심플렉스 기반 방법으로 생성된 솔루션의 구조가 상당히 다르며, 후자의 경우 활성 변수의 지지 집합이 일반적으로 더 작다.^[28]

4. 2. 내부점법 (Interior Point Method)

내부점법(Interior point method])은 나렌드라 카르마르카( नरेंद्र करमरकर^mr, Narendra Karmarkar^영어)가 1984년에 개발한 알고리즘이다. 단체법(심플렉스법)과는 다르게, 실현가능영역(feasible region^영어)의 내부를 통과하는 경로를 따라 최적해를 찾는다.^[1] 이 방법은 선형 계획법에 대해 발견된 최초의 최악의 경우 다항 시간 알고리즘이다. ''n''개의 변수를 가지고 ''L''개의 입력 비트로 인코딩될 수 있는 문제를 해결하기 위해, 이 알고리즘은

O(n^6 L)

시간에 실행된다.

레오니트 카치얀은 1979년 엘립소이드 방법을 도입하여 이 오랜 복잡성 문제를 해결했다. 나움 Z. 쇼르가 개발한 반복법과 아르카디 네미로프스키와 D. 유딘의 근사 알고리즘등 수렴 분석은 (실수) 이전의 방법이 있었다. 카치얀의 알고리즘은 선형 계획법의 다항 시간 내 해결 가능성을 확립하는 데 획기적인 중요성을 지녔다. 하지만, 이 알고리즘은 특히 특별히 구성된 선형 계획법의 경우를 제외하고는 심플렉스 방법보다 효율적이지 않기 때문에, 계산적인 돌파구는 아니었다.

카치얀의 알고리즘은 선형 계획법 분야의 새로운 연구 방향을 제시했다. 1984년, 나렌드라 카르마르카는 선형 계획법을 위한 사영 방법을 제안했다. 카르마르카의 알고리즘^[1]은 카치얀의 최악의 경우 다항식 경계(

O(n^{3.5}L)

을 제공)를 개선했다. 카르마르카는 자신의 알고리즘이 실제 선형 계획법 문제에서 심플렉스 방법보다 훨씬 빠르다고 주장했고, 이 주장은 내점 방법에 대한 큰 관심을 불러일으켰다.^[21] 카르마르카의 발견 이후, 많은 내점 방법들이 제안되고 분석되었다.

이후 내점법은 다양한 연구자들에 의해 발전되었다.

1987년, 바이디아(Vaidya)는 $O(n^3)$ 시간에 실행되는 알고리즘을 제안했다.^[22]
1989년, 바이디아는 $O(n^{2.5})$ 시간에 실행되는 알고리즘을 개발했다.^[23]
2015년, 리와 시드포드는 선형 계획법이 $\tilde O((nnz(A) + d^2)\sqrt{d}L)$ 시간 안에 풀릴 수 있음을 보였다.^[24]
2019년, 코헨(Cohen), 리(Lee) 및 송(Song)은 실행 시간을 $\tilde O( ( n^{\omega} + n^{2.5-\alpha/2} + n^{2+1/6} ) L)$ 시간으로 개선했다.^[25]
리(Lee), 송(Song) 및 장(Zhang)의 후속 연구에서, 그들은 다른 방법을 통해 동일한 결과를 재현했다.^[26]
장(Jiang), 송(Song), 웨인스타인(Weinstein) 및 장(Zhang)의 결과는 $\tilde O ( n^{2+1/6} L)$ 에서 $\tilde O ( n^{2+1/18} L)$ 로 개선되었다.^[27]

현재 의견은 심플렉스 기반 방법과 내부점 방법의 훌륭한 구현의 효율성이 선형 계획법의 일반적인 적용에서 유사하다는 것이다. 그러나 특정 유형의 선형 계획 문제의 경우, 한 유형의 솔버가 다른 솔버보다 더 나을 수 있으며(때로는 훨씬 더 나을 수 있으며), 내부점 방법과 심플렉스 기반 방법으로 생성된 솔루션의 구조가 상당히 다르며, 후자의 경우 활성 변수의 지지 집합이 일반적으로 더 작다.^[28]

5. 활용

선형 계획법은 운영 과학의 여러 실제 문제를 해결하는데 사용된다.^[6] 특히, 네트워크 흐름 문제나 다중 상품 흐름 문제와 같이 특수한 경우에는, 이를 해결하기 위한 특별한 알고리즘이 고안될 정도로 중요하다. 다른 유형의 최적화 문제에 사용되는 많은 알고리즘은 선형 계획법을 통해 대체할 수 있다. 역사적으로 선형 계획법은 쌍대성, 분할, 볼록 해석의 중요성이나 일반화와 같은 최적화 이론의 주요 개념을 이끌어냈다.

선형 계획법은 미시 경제학의 초기 형성에 크게 사용되었으며, 현재는 기업들이 제한된 자원을 효율적으로 활용하여 이윤을 극대화하고 비용을 최소화하기 위해 계획, 생산, 운송, 기술 등 다양한 분야에서 활용하고 있다. 구글(Google)은 유튜브(YouTube) 비디오를 안정화하기 위해 선형 계획법을 사용한다.^[11]

5. 1. 한국에서의 활용 사례

선형 계획법(Linear programming)은 한국의 여러 산업 분야에서 자원 분배, 생산 계획, 비용 절감 등을 위해 널리 활용되고 있다.

'''제조업:''' 생산 라인 최적화를 통해 생산성을 극대화하고, 재고 관리를 효율적으로 수행하며, 원자재 구매 계획을 수립하여 비용을 절감한다.
'''물류:''' 배송 경로 최적화를 통해 운송 비용을 절감하고, 창고 관리를 효율적으로 수행하며, 운송 수단 할당을 최적화하여 자원 낭비를 줄인다.
'''금융:''' 포트폴리오 구성을 최적화하고, 투자 전략을 수립하며, 위험 관리를 통해 투자 손실을 최소화한다.
'''공공 부문:''' 예산 편성을 효율적으로 수행하고, 정책 결정을 위한 의사 결정을 지원하며, 도시 계획 수립에 활용되어 자원 낭비를 줄이고 시민들의 편의를 증진시킨다.
'''에너지:''' 발전소 운영 계획을 최적화하고, 에너지 배분을 효율적으로 수행하며, 신재생 에너지 투자 결정을 지원하여 에너지 효율성을 높인다.

6. 정수 계획법

선형 계획법에서 모든 미지 변수가 정수 값을 가져야 하는 문제를 정수 계획법(IP) 또는 정수 선형 계획법(ILP)이라고 한다. 일반적인 선형 계획법과는 달리, 정수 계획법 문제는 많은 실제 상황에서 NP-난해 문제로 분류된다.
0-1 정수 계획법(또는 이진 정수 계획법, BIP)은 변수가 0 또는 1의 값만 가질 수 있는 정수 계획법의 특수한 경우이다. 이 문제 역시 NP-난해 문제이며, 결정 버전은 카프의 21가지 NP-완전 문제 중 하나였다.

만약 일부 변수만 정수 값을 가져야 하는 경우, 이 문제는 혼합 정수 (선형) 계획법(MIP 또는 MILP) 문제라고 불린다. 이러한 문제는 ILP보다 더 일반적이며, 따라서 일반적으로 NP-난해 문제이다.

하지만, 제약 행렬이 전체 단일 모듈이고 제약의 오른쪽 변이 정수인 경우 등, 효율적으로 해결 가능한 특수한 경우도 존재한다.

정수 선형 계획법을 풀기 위한 고급 알고리즘에는 다음이 포함된다.

절단 평면법
분기 한정법
분기 절단법
분기 가격법

이러한 정수 계획법 알고리즘은 패드버그와 비즐리에 의해 논의되었다.

정수 계획법은 조합 최적화 문제의 일종으로, 스케줄링, 네트워크 설계, 시설 입지 선정 등 다양한 실제 문제 해결에 활용된다.

7. 미해결 문제 및 최근 연구 동향

선형 계획법 이론에는 여러 가지 미해결 문제가 남아있으며, 이러한 문제들의 해결은 수학의 근본적인 발전을 의미하고, 대규모 선형 계획법 문제를 해결하는 능력에 큰 영향을 줄 수 있다. 스티븐 스메일은 21세기의 18가지 가장 위대한 미해결 문제 중 하나로 다음 세 가지 문제를 제시했다.^[29]

강 다항 시간(Strongly polynomial time) 알고리즘을 선형 계획법이 허용하는가?
엄격히 상보적인 해를 찾기 위한 강 다항 시간 알고리즘을 선형 계획법이 허용하는가?
실수(단위 비용) 계산 모델에서 다항 시간 알고리즘을 선형 계획법이 허용하는가?

스메일은 이 중 세 번째 문제가 "선형 계획법 이론의 주요 미해결 문제"라고 말했다. 현재 타원체 방법과 내부점 방법과 같이 약 다항 시간(Weakly polynomial time)으로 선형 계획법 문제를 해결하는 알고리즘은 존재하지만, 제약 조건의 수와 변수의 수에 대해 강 다항 시간 성능을 보장하는 알고리즘은 아직 발견되지 않았다. 이러한 알고리즘의 개발은 이론적으로 매우 중요하며, 실제로도 대규모 선형 계획 문제를 해결하는 데 큰 도움이 될 수 있다.

허쉬 추측(Hirsch conjecture)은 최근 고차원에서 반증되었지만, 여전히 다음 질문들이 남아있다.

다항 시간 심플렉스 변형을 가능하게 하는 피벗 규칙이 존재하는가?
모든 다면체 그래프는 다항적으로 제한된 지름을 가지는가?

이 질문들은 심플렉스 방법과 유사한 알고리즘의 성능 분석 및 개발과 관련이 있다. 심플렉스 알고리즘은 이론적으로는 지수 시간이 걸리지만, 실제로는 매우 효율적이기 때문에, 다항 시간 또는 강 다항 시간으로 실행되는 심플렉스 알고리즘의 변형이 존재할 가능성이 있다. 이러한 변형의 존재 여부는 선형 계획법을 강 다항 시간 내에 해결할 수 있는지 여부를 결정하는 데 중요한 접근 방식이 될 수 있다.

심플렉스 알고리즘과 그 변형은 선형 계획법 문제를 다면체의 엣지를 따라 정점에서 정점으로 이동하여 해결하기 때문에 엣지를 따라가는 알고리즘(edge-following algorithm)이라고 불린다. 이 알고리즘들의 이론적 성능은 LP 다면체의 임의의 두 정점 사이의 최대 엣지 수에 의해 제한되므로, 다면체 그래프 이론적 지름의 최대치를 파악하는 것이 중요하다. 모든 다면체가 하위 지수 지름을 갖는다는 것은 증명되었으며, 최근 허쉬 추측의 반증은 임의의 다면체가 초다항 지름을 갖는지 증명하기 위한 첫 단계이다. 만약 그러한 다면체가 존재한다면, 어떤 엣지를 따라가는 변형도 다항 시간 내에 실행될 수 없다. 다면체 지름에 대한 질문은 그 자체로도 중요한 수학적 문제이다.

심플렉스 피벗 방법은 주(primal) 실행 가능성 또는 쌍대(dual) 실행 가능성을 유지한다. 반면에, 크리스 크로스 피벗 방법(criss-cross pivot method)은 주 실행 가능성이나 쌍대 실행 가능성을 유지하지 않고, 임의의 순서로 주 실행 가능, 쌍대 실행 가능, 또는 주/쌍대 모두 실행 불가능한 기저(basis)를 방문할 수 있다. 이러한 유형의 피벗 방법은 1970년대부터 연구되어 왔다.^[29] 이 방법은 선형 계획법 문제에서 배열 다면체(arrangement polyhedron)의 최단 피벗 경로를 찾으려고 시도한다. 배열 다면체의 그래프는 작은 지름을 갖는 것으로 알려져 있어, 일반적인 다면체의 지름에 대한 문제를 해결하지 않고도 강 다항 시간 크리스 크로스 피벗 알고리즘이 존재할 가능성이 있다.^[19]

참조

_[1] 논문 A Model of General Economic Equilibrium
_[2] 논문 A Generalization of the von Neumann Model of an Expanding Economy
_[3] 서적 General Equilibrium and Structural Dynamics: Perspectives of New Structural Economics Economic Science Press
_[4] 서적 Linear and Integer Optimization: Theory and Practice CRC Press
_[5] 웹사이트 Linear programming {{!}} Definition & Facts {{!}} Britannica https://www.britanni[...] 2023-11-20
_[6] 논문 Reminiscences about the origins of linear programming https://apps.dtic.mi[...] 1982-04
_[7] 서적 Theory of Linear and Integer Programming John Wiley & Sons
_[8] 서적 Linear programming Springer 1997
_[9] 논문 A Polynomial Algorithm for Linear Programming 1979
_[10] 논문 A New Polynomial-Time Algorithm for Linear Programming 1984
_[11] 서적 CVPR 2011 https://static.googl[...] 2011
_[12] 문서
_[13] 문서
_[14] 문서
_[15] 문서
_[16] 문서
_[17] 문서
_[18] 문서
_[19] 논문 Criss-cross methods: A fresh view on pivot algorithms
_[20] 논문 An exponential example for Terlaky's pivoting rule for the criss-cross simplex method
_[21] 논문 Karmarkar's algorithm and its place in applied mathematics 1987-06-01
_[22] 학술회의 An algorithm for linear programming which requires ${O} (((m+ n) n^2+(m+ n)^{1.5} n) L)$ arithmetic operations
_[23] 학술회의 30th Annual Symposium on Foundations of Computer Science
_[24] 학술회의 Efficient inverse maintenance and faster algorithms for linear programming
_[25] 학술회의 Solving Linear Programs in the Current Matrix Multiplication Time
_[26] 학술회의 Solving Empirical Risk Minimization in the Current Matrix Multiplication Time
_[27] 학술회의 Faster Dynamic Matrix Inverse for Faster LPs
_[28] 논문 Pivot versus interior point methods: Pros and cons https://strathprints[...]
_[29] 논문 A Monotonic Build-Up Simplex Algorithm for Linear Programming 1994
_[30] 웹사이트 lp_solve reference guide (5.5.2.5) https://web.mit.edu/[...] 2023-08-10
_[31] 웹사이트 External Language Interfaces http://lpsolve.sourc[...] 2021-12-03
_[32] 웹사이트 lp_solve command http://lpsolve.sourc[...] 2021-12-03
_[33] 웹사이트 COR@L – Computational Optimization Research At Lehigh http://coral.ie.lehi[...]
_[34] 문서 OptimJ used in an optimization model for mixed-model assembly lines, University of Münster http://www.in-ter-tr[...]
_[35] 문서 OptimJ used in an Approximate Subgame-Perfect Equilibrium Computation Technique for Repeated Games http://www.aaai.org/[...]

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com